#include <iostream>
#include <string>

using namespace std;

/**
 * 文法产生式如下
 * E ->  TE'
 * E'->  ATE' | ε
 * T ->  FT'
 * T'->  MFT' | ε
 * F ->  (E) | i
 * A ->  + | -
 * M ->  * | /
 ----------------
 * 状态转换表如下
 * |    |   i   |   (   |  )   |    +    |    -    |    *    |    /    |  $   |
 * |:--:| :---: | :---: | :--: | :-----: | :-----: | :-----: | :-----: | :--: |
 * | E  | E→TE' | E→TE' |      |         |         |         |         |      |
 * | T  | T→FT' | T→FT' |      |         |         |         |         |      |
 * | E' |       |       | E'→ε | E'→ATE' | E'→ATE' |         |         | E'→ε |
 * | A  |       |       |      |   A→+   |   A→-   |         |         |      |
 * | F  |  F→i  | F→(E) |      |         |         |         |         |      |
 * | M  |       |       |      |         |         |   M→*   |   M→/   |      |
 * | T' |       |       | T'→ε |   T'→ε  |   T'→ε   | T'→MFT' | T'→MFT' | T'→ε |
 */

bool haveError = false;
string products[50][50] = { // NOLINT
        /*  i       (        )      +        -       *      /       $    */
        { "Te",   "Te",   "null", "null", "null", "null", "null", "null", }, // E
        { "Ft",   "Ft",   "null", "null", "null", "null", "null", "null", }, // T
        { "null", "null", "ε",    "ATe",  "ATe",  "null", "null", "ε", },    // E'
        { "null", "null", "null", "+",    "-",    "null", "null", "null", }, // A
        { "i",    "(E)",  "null", "null", "null", "null", "null", "null", }, // F
        { "null", "null", "null", "null", "null", "*",    "/",    "null", }, // M
        { "null", "null", "ε",    "ε",    "ε",    "MFt",  "MFt",  "ε", }      // T'
}; // 存放各个表达式右部

char Vn[200] = "ETeAFMt"; // e == E', t == T'
char Vt[200] = "i()+-*/$";

void analyze(string& exp);

int findVn(char c);

int findVt(char c);

void readLexicalResult(string& exp);

int main(int argc, char** argv)
{
    if (argc < 2)
    {
        cout << "Too few arguments." << endl;
        return 1;
    }
    string path{ argv[1] };
    string name = path.substr(0, path.length() - 7); // 去掉后缀名
    string exp; // 从词法分析中读出的表达式

    freopen(path.c_str(), "r", stdin); // 重定向输入
    freopen((name + "_ll1.txt").c_str(), "w", stdout); // 重定向输出

    readLexicalResult(exp);
    cout << "The Expression is: " << exp << endl;
    analyze(exp);

    if (haveError)
        cout << "!!!This Expression is ILLEGAL!!!" << endl;
    else
        cout << "...This Expression is CORRECT..." << endl;
    return 0;
}

void analyze(string& exp)
{
    int step = 1; // 输出Step
    int i = 0;
    char procStack[20] = "$E"; // 输出stack，为了方便输出用数组模拟
    int stackTop = 2;
    printf("%-5s%-10s%-15s%s\n", "Step", "Stack|->", "Expression", "Production");

    while (i < exp.length())
    {
        int x, y;
        char ch = procStack[stackTop - 1];
        string procStackTop{ ch };
        x = findVn(ch);
        y = findVt(exp[i]);
        if (x != -1) // 栈顶的不是终结符号
        {
            procStack[stackTop--] = '\0';
            if (y != -1) // 表达式下一个符号是合法终结符号
            {
                string product = products[x][y]; // 选择产生式
                if (product == "null") // 选不到产生式，报错
                {
                    printf("%-5d%-10s%-15s%s\n", step, procStack, exp.c_str() + i, "(ERROR: Production NOT Match)");
                    step++;
                    haveError = true;
                    procStack[stackTop++] = ch; // 原非终结符号压回栈
                    ++i; // 舍弃此终结符号
                    continue;
                }
                printf("%-5d%-10s", step, procStack);

                if (product != "ε") // 产生式右部入栈
                    for (int q = product.length() - 1; q >= 0; q--) // NOLINT
                        procStack[stackTop++] = product[q];
                else
                    procStack[stackTop] = '\0';
                printf("%-15s%-10s\n", exp.c_str() + i, (procStackTop.append("->").append(product)).c_str()); // 输出仍未匹配表达式序列与产生式
            }
            else // 表达式下一个符号是非法终结符号
            {
                printf("%-5d%-10s%-15s%s\n", step, procStack, exp.c_str() + i, "(ERROR: ILLEGAL Terminate Symbol)");
                step++;
                haveError = true;
                procStack[stackTop++] = ch; // 原非终结符号压回栈
                ++i; // 舍弃此终结符号
                continue;
            }
        }
        else // 栈顶出现终结符号
        {
            if (ch == exp[i])
            {
                --stackTop;
                printf("%-5d%-10s", step, procStack);
                if (ch == '$' && exp[i] == '$')
                {
                    printf("%-15s%-10s\n", "$", "(Accept)");
                    return;
                }
                printf("%-15s(%c %s\n", exp.c_str() + i, ch, "Matched)");
                procStack[stackTop] = '\0';
                ++i;
            }
            else
            {
                printf("%-10s\n", "ERROR");
                ++i;
                continue;
            }
        }
        step++;
    }
}

void readLexicalResult(string& exp) // 提取词法分析得到的序列
{
    char c;
    string type, word;
    while (cin >> c)
    {
        if (' ' != c) // 过滤空格
            if (c == '<')
            {
                cin >> type >> word;

                if (type == "ID," || type == "NUM,") // 立即数与标识符均视为标识符
                    exp += 'i';
                else if (type == "OP," || (type == "SEP," && (word == "(>" || word == ")>")))
                    exp += word.substr(0, word.length() - 1); // 去除读到的最后一个 >
                else // 非法词汇字符均视为@
                    exp += '@';
            }
    }
    fclose(stdin);
    exp += '$'; //结尾加$
}

int findVn(char c)
{
    for (int i = 0; i < 7; i++) //找到产生式对应行
        if (c == Vn[i])
            return i;
    return -1;
}

int findVt(char c)
{
    for (int i = 0; i < 8; i++) //找到产生式对应列
        if (c == Vt[i])
            return i;
    return -1;
}
